package code.sort;

import java.util.Arrays;

public class QuickSort {
    /**
     * 快速排序，a是数组，n表示数组的大小
     * @param a
     * @param n
     */
    public static void quickSort(int[] a, int n){
        quickSortInternally(a, 0, n-1);
    }

    private static void quickSortInternally(int[] a, int p, int r) {
        if (p >= r){
            return;
        }
        //获取分区点
        int q = partition(a, p, r);
        quickSortInternally(a, p, q-1);
        quickSortInternally(a, q+1, r);
    }

    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for (int j=p ; j < r; j++){
            if (a[j] < pivot){
                if (i == j){
                    i++;
                }else{
                    //swap
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                    i++;
                }
            }
        }

        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;

        return i;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 2, 1, 5, 6, 7, 8};
        quickSort(array, array.length);
        System.out.println(Arrays.toString(array));
    }
}
